#include <iostream>
#include <unordered_map>
using namespace std;

/**
 * 借助一个【双向链表】数据结构
 */
struct DLinkedNode {
  int key, value;
  DLinkedNode* prev;
  DLinkedNode* next;
  DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr) {}
  DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr) {}
};

class LRUCache
{
private:
  /// 借助一个 map 避免【遍历链表】查找 key 对应的 DLinkedNode
  unordered_map<int, DLinkedNode*> map;
  /// 双向链表的【头】=> 最久【未】使用的
  DLinkedNode* head;
  /// 双向链表的【尾】=> 最【新使用】过的
  DLinkedNode* tail;
  ///【当前】双向链表的【长度】
  int size;
  ///【最大】双向链表的【长度】，当 size > capacity 时，那么要【淘汰】一个元素
  int capacity;

public:
  LRUCache(int _capacity): capacity(_capacity), size(0), head(nullptr), tail(nullptr)
  {}

  int get(int key)
  {
    DLinkedNode* n = map[key];
    if (!n) return -1;

    // 将 n 调整到 双向链表的【头部】
    bringToHead(n);

    return n->value;
  }

  void put(int key, int value)
  {
    DLinkedNode* n = map[key];

    if (n)
    {
      n->value = value;
    }
    else
    {
      n = new DLinkedNode(key, value);
      map[key] = n;
    }

    bringToHead(n);
    removeTail();
  }

  void bringToHead(DLinkedNode* n)
  {
    if (!head)
    {
      head = tail = n;
      return;
    }

    if (head == n)
      return;

    if (tail == n)
    {
      if (n->prev)
        n->prev->next = nullptr;
      tail = n->prev;
      n->prev = nullptr;

      head->prev = n;
      n->next = head;
      head = n;

      return;
    }

    if (n->prev)
      n->prev->next = n->next;
    if (n->next)
      n->next->prev = n->prev;

    head->prev = n;
    n->next = head;
    head = n;
  }

  void removeTail()
  {
    if (!tail) return;

    /// 必须大于规定长度，才执行淘汰
    if (size <= capacity) return;

    /// 先记录下要删除的节点
    DLinkedNode* n = tail;

    /// map 删除节点
    map.erase(n->key);

    /// 双向链表 删除节点
    if (tail->prev)
    {
      tail->prev->next = nullptr;
    }
    delete n;
  }
};

int main(int argc, char const *argv[])
{
  LRUCache* cache = new LRUCache(2);

  cache->put(1, 1);
  cache->put(2, 2);
  cache->get(1);       // 返回  1
  cache->put(3, 3);    // 该操作会使得关键字 2 作废
  cache->get(2);       // 返回 -1 (未找到)
  cache->put(4, 4);    // 该操作会使得关键字 1 作废
  cache->get(1);       // 返回 -1 (未找到)
  cache->get(3);       // 返回  3
  cache->get(4);       // 返回  4


  return 0;
}
